Visualization of three-dimensional data using a variety of two dimensional projections as well as stereo viewing techniques is well known in scientific and engineering communities. Much data exists in a form that has come to be known as point cloud data, and which is obtained as a result of a multitude of discrete point measurements. Typically, such measurements may be taken from an aircraft or possibly a satellite overflying an area and using a beam transmitter, such as radar, lidar or other scanning equipment, for generating a beam that will develop one or more returns back to the transmitter upon striking a surface beneath the aircraft or satellite. Such equipment is conventionally available today, and is computerized so that information related to attitude and altitude of the aircraft is automatically embedded into the point cloud data recorded by the scanning equipment. The instant invention provides new algorithms and techniques for converting point cloud data to a variety of raster images for analysis and visualization, as well as methods for accessing point cloud data faster than has hitherto been possible.
One specific application area is in processing data from laser range finders, also known as light detection and ranging (LIDAR), or laser detection and ranging (LADAR) devices, although the novel techniques disclosed herein have general applicability to point cloud data from other sensors or data generated by manual surveys or other techniques. The term “point cloud data” generally refers to data organized such that one or more spatial coordinates, or locations, of each measured point in a point cloud are included along with other data related to that point. Such other data may include, by way of example, range, temperature, light intensity and any other parameter that may be developed from a beam return. Such a grouping of data associated with a single point measurement, or return, and which includes location of that point is known in the art as a “tuple”. Spatial coordinates of tuples in a point cloud are typically expressed in some appropriate reference system, which may, for example, be Cartesian, spherical, or any of several geodetic coordinate reference systems. As noted, other parameters in a tuple in addition to location may include such items as range, temperature, intensity, or other attributes or parameters associated with that particular spatial location under measurement. For example, a one-dimensional data tuple organization for a wire or rod might include data elements as represented by fields shown in Table 1:
TABLE 1Field NameMeaningXDistance as measured from theoriginTTemperaturepDensityKConductivityThis example would be a 4-tuple in that there are 4 values per data tuple sample or measurement. Note that for each tuple, a spatial component, or location where the measurement is taken along the wire or rod is included (X, in the example above) and is not required to be uniformly spaced along the wire or rod as would be the case in a raster or other similar system. As shown in FIG. 1, 2-dimensional gridded raster data 10, such as would be obtained from a CCD array or other scanning system wherein data is collected along uniformly spaced points, is contrasted with quasi-random point cloud tuple data 12 that has no uniformly organized arrangement. In this example, a temperature measurement is included with location measurements. Thus, as an advantage of point cloud analysis, it should be apparent that when dealing with a point cloud containing point cloud data tuples, only data associated with each tuple is computationally considered, rather than having to consider “empty” or meaningless tuple locations from every point in a field of tuples, such as found a raster system, CCD array or other such 2-dimensional fields wherein data points therein are arranged in a predetermined manner. Note that while a two dimensional example is used here, the general discussion applies to any dimensionality of data. In addition, gridded data need not be necessarily spaced on a linear, uniform axis. It is only necessary that an a priori method exist to map numerical data to respective sub-sets of its dimensions. This is commonly seen in gridded data where one or more of the axes are logarithmic. Notice in FIG. 1 that X, Y spacing of points in a grid 10 is assumed, due to grid organization, and thus it is not necessary to store actual <X, Y> coordinates for each point. In this system of gridded data relating to temperature, it is only necessary to store the temperature (<T>) value at each measured point in the grid. In point cloud data, spatial organization of the data is not uniform, and therefore it is necessary to store X and Y coordinates, along with Temperature, for each measured point, resulting in three-tuples containing data <X, Y, T>. It is thus apparent that gridded data have an advantage in storage efficiency whereas point cloud data have the flexibility of non-uniform spacing.
The instant invention is concerned primarily with point cloud data tuples having 2 or 3 spatial locations, and in some instances a time dimension, although some algorithms of the instant invention can be applied to data with other spatial dimensionality. Algorithms disclosed herein can carry along any number of attributes for each tuple in addition to spatial, and possibly time coordinates. In the 1-dimensional example above (Table 1), there is a single spatial dimension (X) and three attribute fields (T, p and K). In this discussion these data are considered to have one spatial dimension.
Spatially unorganized data for a volume and containing tuples comprising 3 spatial coordinate locations and optionally a time value along with associated attribute fields are often referred to as “point clouds” when the tuples are considered to be of infinitesimal spatial extent, or “voxel (Volumetric Cell) clouds” when the tuples are considered to have finite spatial extent. This nomenclature arises from the fact that the data are usually (although not necessarily) spatially irregular and spatially unorganized. An example of this sort of data could be that derived from a lidar or other laser scanner at an altitude and being used to collect information about the surface of the Earth. A table of possible data collected therefrom depicted in Table 2.
TABLE 2Field NameMeaningXX distance from the originYY distance from the originZZ distance from the originTTime of acquisition of the pointRReflectivity of the laser pulseCSurface classificationNReturn numberSTotal number of returns for thispulseMMirror angle of sensor
This example is not meant to be inclusive of every laser or beam scanning system, but rather is used to point out differences between tuple organized data and a typical raster organization. The important differences are that the tuple organized data are usually irregular in their spatial organization and typically carry significantly more attribute fields than do data associated with points in a typical raster image. However, it must be recognized that the algorithms and techniques of the instant invention apply also to the degenerate case in which the tuple or point cloud data are uniformly spaced.
In discussions and developments that follow, the general term “point cloud” is used to refer to tuples of data that carry information regarding their spatial locations. The term “raster” or “uniform raster” is used herein to refer to data tuples in which one or more of the spatial coordinates are predetermined via some a priori organization and thus are omitted from the tuples themselves. Hybrid data tuples where the <X, Y> coordinates are not stored, but the <Z> coordinate is stored, are considered to be raster data.
Common Techniques of Visualizing Spatial Tuple Data
There are a number of prior art techniques for visualizing and manipulating point cloud (spatial tuple) data, these techniques being embodied in quite a number of commercial and non-commercial software visualization tools available today. General approaches in use today are rasterization viewing, point cloud viewing, surface model viewing in two dimensions, and stereo visualization of orthophotos that have been generated from point cloud data. Stereo visualization of an orthophoto requires the additional step of rendering a stereo mate to the orthophoto using a synthetic camera position. In contrast, Applicants generate stereo pair imagery directly from point cloud data as a single process.
Rasterization viewing from point cloud data is developed by converting non-uniformly spaced point cloud data into a uniform raster rendition. To accomplish such rendition, a variety of techniques may be employed, with a simplest technique being to superimpose non-uniform point cloud data over a grid of appropriate spacing and ‘poke’ point cloud data into the grid. Here, location of data in each tuple is used to determine where the other, measured data in the tuple is to be inserted into the grid. For example, if one had a four-tuple of (X, Y, Z and T) where T is temperature, then a visual rendition might be a ‘stack’ of raster images, with each layer of the stack corresponding to a range of Z. The temperature value T is ‘poked’ into a raster grid intersection closest to the tuple X, Y values, and may be depicted as an intensity representation. A large number of variations of this technique are possible with gray shading and color being used to represent an attribute or dimensional data.
Point cloud viewing of the prior art is usually some variant of projecting three dimensional data onto a plane using a projection algorithm and then displaying this projection on a computer monitor, with attributes such as color, point size, rendering style and so forth being used to visualize attribute data.
Surface modeling of the prior art involves changing the nature of data through a rendering algorithm. For example, 3-tuple data that represents simply X, Y and Z location values can be rendered as contour profiles and displayed in a two dimensional rendering such as a computer display or a paper contour map.
Stereo visualization involves presenting data to a user through some interface mechanism such that a slightly different perspective of the data is individually presented to the left and right eyes. A result is a perception of depth by an observer, simulating normal human binocular vision. A general approach to stereo visualization, as depicted in FIG. 2, is to process three dimensional information 20 into a pair 22, 24 of two dimensional renditions, one (22) perspective for observation by the left eye and a second (24) from a slightly different perspective for observation by the right eye. Such a set of images is typically referred to as a “Stereo Pair.” A variety of different approaches have been developed for viewing these stereo pairs. A familiar example is a classic ViewMaster™ toy in which two images each from a slightly different perspective are presented individually to left and right eyes of an observer by an optical-mechanical binocular viewing device. A second simple example is rendering two separate images in different colors and then observing the images through a pair of glasses containing lenses or filters made of two different color films that transmit information from the desired image to the desired eye (anaglyphic stereo). More complex examples of stereo viewing are active computer systems that use a headset or goggles implement a form of dynamic polarization to alternately occlude right and left eyes of an observer as images on a computer monitor are synchronously switched between a left image and right image, respectively.